#include<stdio.h>
#include<malloc.h>
#include<stdlib.h> 
  

   struct node                            //Structure containing data and next part..
 {
   int data;
   struct node *next;
 }*p;
 
int ctr=0;

delete(int num)
 {
     struct node *temp, *m;
     temp=p;
      while(temp!=NULL)
    {
       if(temp->data==num)
       {
           if(temp==p)
           {
              p=temp->next;
              free(temp);
            return; 
           }
           else
         {
           m->next=temp->next;
           free(temp);
           return;
         }
      }else
        {
           m=temp;
          temp= temp->next;   
        }
ctr--;
}
    printf("\n ELEMENT %d NOT FOUND ", num);
} 

int pop(int loc)
{ struct node *temp,*last;
  if(loc==0)
   { temp=p;
     p=temp->next;
     return (temp->data);
     free(temp);
     ctr=ctr-1;
}
 else if(loc==ctr)
{ int i; 
temp=p;
   for(i=0;i<loc-1;i++)
  {  temp=temp->next;
   }
  last=temp->next; 
  return (last->data);
  free(last);
  ctr=ctr-1;
  temp->next=NULL;
  
}
else
{ int i; 
 temp=p;
 for(i=0;i<loc-1;i++)
  {  temp=temp->next;
   }
  last=temp->next; 
  
  temp->next=last->next;
  return (last->data);
  free(last);
  ctr=ctr-1;
}

}
   


     

 void append( int num )
 {
     struct node *temp,*r;
       ctr++;
       temp= (struct node *)malloc(sizeof(struct node));
       temp->data=num;
       r=(struct node *)p;

      if (p == NULL) 
     {
         p=temp;
         p->next =NULL;
     }
  else
     {        

       while( r->next != NULL)
       r=r->next;
       r->next =temp;
       r=temp;
       r->next=NULL;
     }
  
}

 int count_n(int num)
{ int c=0;
  struct node *temp;
  temp=p;
  while( temp!=NULL)
 { if(temp->data==num)
   { c++;
      temp=temp->next;
}
else { temp=temp->next; }
}
return c;
}
 insert(int loc, int num)
  {
     int i;
     struct node *temp,*t,*r;
     r=p;       
      if(loc > ctr+1 || loc < 0)
   {
         printf("insertion is not possible :");
            return;
   }
       else if (loc == 0)
         {
           
           temp=(struct node *)malloc(sizeof(struct node));
           temp->data=num;     

       
            if(p==NULL)
         {
          p=temp;
          p->next=NULL;
         }
            
            else
         {
          temp->next=p;
          p=temp;
            }
         ctr++;
       return;
         }
      else
 {
       for(i=0;i<loc;i++)
          {
             t=r;  
             r=r->next;
          }
         temp=(struct node *)malloc(sizeof(struct node));
         temp->data=num;
         t->next=temp;
         t=temp;
         t->next=r;
       ctr++; 
       return;
       }
}

  display(struct node *r)
  {
      r=p;
      if(r==NULL)
     {
       printf("[]");
       return;
     }
      printf("["); 

       while(r!=NULL)
    {
      printf("%d ",r->data);
      r=r->next;
    }
     printf("]");
  }
int index1(int x)
{ int i=0;
  while((p!=NULL) && (p->data!=x))
  {   i++;
      p=p->next;

}
return i; 
}  
void length()
 {
   struct node *n;
   
   n=p;
    while(n!=NULL)
   {
     n=n->next;
     ctr++;
   }
  
 }
//FUNCTION TO REVERSE THE LIST
reverse(struct node *q)
{
   struct node *m, *n,*l,*s;
   m=q;
   n=NULL;
  while(m!=NULL)
 {
   s=n;
   n=m;
  m=m->next;
  n->next=s;
 }
   p=n;
}
/*void b_sort()
{  int i,j;
  struct node *p1, *p2, *p3;
for(i = 1; i < ctr; i++)
{
    p1 = p;
    p2 = p->next;
    p3 = p2->next;
  
    for(j = 1; j <= (ctr - i); j++)
    {
       if(p2->data < p3->data)  
       {
           p2->next = p3->next;
           p3->next = p2;
           p1->next = p3;
           p1       = p3;
           p3       = p2->next;
       }
       else
       {
           p1 = p2;
           p2 = p3;
           p3 = p3->next;
       }
    }
}
}
*/
void b_sort()
{
int i,j;
struct node *p1,*temp;
temp= (struct node *)malloc(sizeof(struct node));
p1= (struct node *)malloc(sizeof(struct node));
p1=p;
for(i=0;i<ctr;i++)
{  p=p->next;
   for(j=i;j<ctr;j++)
   { p1=p1->next;
     if((p->data)>(p1->data))
      { 
        temp->data=p->data;
        p->data=p1->data;
        p1->data=temp->data;
}
}
}
}

/*  MAIN FUNCTION  */

  main()
 {
        int i,num,x,j,k;
   p=NULL;
   struct node *n;
   do
 {
    
    
    printf("\n 1.APPEND AN ELEMENT INTO THE LIST:");
    printf("\n 2.INSERT A NUMBER AT A PARTICULAR LOCATION IN THE LIST:");
    printf("\n 3.PRINT THE LIST :");
    printf("\n 4.PRINT THE NUMBER OF ELEMENTS IN THE LIST  ");
    printf("\n 5.REMOVE AN ELEMENT FROM THE LIST:");
    printf("\n 6.REVERSE THE LIST :");
    printf("\n 7.POP THE ELEMENT AT PARTICULAR LOCATION:");
    printf("\n 8.COUNT NO. OF OCCURENCES OF AN ELEMENT:");
    printf("\n 9.EXTEND THE LIST :");
    printf("\n 10.FIND INDEX OF THE FIRST OCCURENCE OF AN ELEMENT :");
    printf("\n 11.SORT THE LIST :");
    printf("\n 12.EXIT:");
    printf("\n PLEASE, ENTER YOUR CHOICE:");
    scanf("%d",&i);

      switch(i)
    {      
          case 1: 
                   printf("\n PLEASE ENTER THE NUMBER :-");
                   scanf("%d",&num);
                   append(num);
                   break;
       

          case 2: 
                  printf("PLEASE ENTER THE NUMBER :-");
      		  scanf("%d",&x);
      		  printf("PLEASE ENTER THE LOCATION NUMBER :-");
      	          scanf("%d",&j);
                  insert(j,x);
                  break;
          case 3: printf("\n THE  ELEMENTS IN THE LIST ARE : ");
         	  display(n);
         	  break;
      

          case 4: 
                  display(n);
                  printf(" TOTAL NO OF ELEMENTS IN THE LIST ARE %d",ctr);
      		  break;
          case 5: 
                  printf("PLEASE ENTER A NUMBER FROM THE LIST :");
      		  scanf("%d",&num);
      		  delete(num);
     		  break;
    
   	  case 6: reverse(p);
        	  display(p);
        	  break;
 
          case 7: 
                  printf("\n ENTER THE LOCATION WHOSE ELEMENT IS TO BE POPPED:");
                  scanf("%d",&j);
                  printf("DELETING %d",pop(j));
                  break; 
         case 8:  printf("PLEASE ENTER A NUMBER FROM THE LIST :");
                  scanf("%d",&num);
                  printf("NO. OF TIMES %d OCCURS IN THE LIST=%d",num,count_n(num));
                  break; 
         case 9:  printf("ENTER no. of ELEMENTS IN THE NEW LIST:");
                  scanf("%d",&k);
		  printf("ENTER ELEMENTS IN THE NEW LIST:");
                  for(i=0;i<k;i++)
		  {        scanf("%d",&j);
                          append(j);  
                        }
		  break;
        case 10:  printf("ENTER ELEMENT WHOSE INDEX IS REQUIRED:");
		  scanf("%d",&j);
                  printf("\n INDEX OF %d IS=%d",x,index1(j));
		  break;
        case 11:  printf("\n THE SORTED LIST IS:");
                  b_sort();
                  display(p);
                  break;   
        case 12:  exit(0);
    }
 }while((i>=1)&&(i<=11));
}
